package com.example.demo.leetcode;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/01 9:57
 */
public class _438_找到字符串中所有字母异位词 {

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        String s1 = "abab";
        String p1 = "ab";
        List<Integer> anagrams = findAnagrams1(s1, p1);
        anagrams.forEach(System.out::println);
    }

    public static List<Integer> findAnagrams(String s, String p) {
        int[] pArr = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pArr[p.charAt(i) - 'a']++;
        }

        List<Integer> res = new ArrayList<>();
        int[] tempArr = new int[26];
        for (int i = 0; i < s.length(); i++) {
            tempArr[s.charAt(i) - 'a']++;
            if ((i >= p.length() - 1)) {
                //判断是否相等
                if (Arrays.equals(pArr, tempArr)) {
                    res.add(i - (p.length() - 1));
                }
                tempArr[s.charAt(i - (p.length() - 1)) - 'a']--;
            }
        }
        return res;
    }

    public static List<Integer> findAnagrams1(String s, String p) {
        List<Character> pList = new ArrayList<>();
        for (int i = 0; i < p.length(); i++) {
            pList.add(p.charAt(i));
        }
        pList.sort(Character::compare);

        List<Integer> res = new ArrayList<>();
        List<Character> tempList = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            tempList.add(s.charAt(i));
            if (pList.size() == tempList.size()) {
                //判断是否相等
                tempList.sort(Character::compare);
                if (pList.toString().equals(tempList.toString())) {
                    res.add(i - (p.length() - 1));
                }
                tempList.remove((Character) s.charAt(i - (p.length() - 1)));
            }
            i++;
        }
        return res;
    }


}
